__author__ = 'wlee'
import Pycluster
import random
from collections import deque
import numpy
import math
checkins = open('Brightkite_totalCheckins.txt','rb')
kmlstatement=[]
geos=[]
geo_avgs=dict()
id=0
count = 0
valid_ids =[]

write_valid_ids = open('valid_ids2.txt','wb')
us_num = 0

def check_similarity(u):

    lats = numpy.zeros(len(u))
    longs = numpy.zeros(len(u))

    if u!=0:
        for i in range(len(u)):
            lats[i] = u[i][0]
            longs[i] = u[i][1]

    similarity_lats = numpy.var(lats)
    similarity_longs = numpy.var(longs)

   
    
    if similarity_lats > 0.5:
        return False
    if similarity_longs > 0.5:
        return False

    return True


def calculate_mean(u):
    lats = numpy.zeros(len(u))
    longs = numpy.zeros(len(u))

    if u!=0:
        for i in range(len(u)):
            lats[i] = u[i][0]
            longs[i] = u[i][1]

    return numpy.mean(lats),numpy.mean(longs)



def won_cluster(geos):

    results =[]
    index_queue = deque()
    index_queue.append(0)

    geo_locations = dict()
    geo_locations[0]=geos
    while len(index_queue):

        current_id=index_queue.pop()
        current_items= geo_locations[current_id]
        info= Pycluster.kcluster(current_items,2)

        index = info[0]



        count = 0

        left_list = []

        right_list =[]

        left_count = 0
        right_count = 0

        for geo_item in current_items:

            if index[count] == 0:
                left_list.append(geo_item)
                left_count +=1
            if index[count] == 1:
                right_list.append(geo_item)
                right_count +=1

            count +=1


        if check_similarity(left_list) == False:
            index_queue.append(2*current_id +1)
            geo_locations[2*current_id +1]=left_list

        else:
            l = calculate_mean(left_list)
            results.append([l[0],l[1]])


        if check_similarity(right_list) == False:
            index_queue.append(2*current_id +2)
            geo_locations[2*current_id +2]=right_list

        else:
            r = calculate_mean(right_list)
            results.append([r[0],r[1]])

    return results

      




     


for checkin in checkins:

    parsed_info= checkin.split("\t")

    if len(parsed_info)<3:
        continue

    if str(id) == str(parsed_info[0]):

       
        if len(parsed_info[2])<3:
            continue
            

        lat = float(parsed_info[2])
        lng = float(parsed_info[3])

        if -124< float(lng) and -60>float(lng):
            if  17< float(lat) and 49> float(lat):
                geo = [parsed_info[2],parsed_info[3]]
                geos.append(geo)

    else:

            lat = float(parsed_info[2])
            lng = float(parsed_info[3])
            count = 0
            num_check = []
            temp_geo=[]

            if len(geos)>=2:
                clustered_groups= won_cluster(geos)
                if len(clustered_groups)<5:
                    for g in clustered_groups:
                        write_valid_ids.write(str(int(id))+"\t"+str(g[0])+"\t"+str(g[1])+"\n")

                #print id,len(clustered_groups)
            
            id = parsed_info[0]

            if -124< float(lng) and -60>float(lng):
                if  17< float(lat) and 49> float(lat):
                    geo = [parsed_info[2],parsed_info[3]]
                    geos = []
                    geos.append(geo)
print us_num




